package com.ai.zuochengyun.phase01.class01;

/**
 * 找到数组中的局部最小值
 */
public class Code04_BinarySearchUnorderedArray {

    public static void main(String[] args) {
        int times = 4;
        for (int i = 0; i < times; i++) {
            int size = (int) (Math.random() * 50) + 1;
            int[] arr = new int[size];
            for (int j = 0; j < size; j++) {
                arr[j] = (int) (Math.random() * 50) + 1;
                System.out.print(arr[j] + " ");
            }
            System.out.println();
            int index = getLessIndex(arr);
            System.out.println(index);
            System.out.println("========================");
        }
    }


    private static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        int left = 1;
        int right = arr.length - 2;
        while (left < right) {
            int mid = left + (right - left) >> 1;
            if (arr[mid - 1] < arr[mid]) {
                // mid左边的值比mid位置的值小，往左边继续找
                right = mid - 1;
            } else if (arr[mid + 1] < arr[mid]) {
                // mid右边的值比mid位置的值大，往右边继续找
                left = mid + 1;
            } else {
                // mid位置的值比左边和右边都小，那么就返回mid位置的值
                return mid;
            }
        }
        return left;
    }
}
